package com.monkeyboy.stack;

import java.util.*;

/**
 * 大小为 K 的最小堆
 * <p>
 * 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，
 * 则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
 *
 * 解题思路：
 * 1. 使用优先级队列，默认升序排列
 * 2. 使用快速排序
 *
 * @Author Gavin
 * @date 2021.03.31 09:54
 */
public class Stack03 {
    public ArrayList<Integer> get(int[] nums, int k) {
        if (k > nums.length || k <= 0) {
            return new ArrayList<>();
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(((o1, o2) -> o2 - o1));//降序排列，默认升序
        for (int num : nums) {
            maxHeap.add(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }

    //利用快速排序
    public ArrayList<Integer> getByFast(int[] nums, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        FastOrder fastOrder = new FastOrder();
        fastOrder.asc(nums);//传递的是引用，所以nums里面已经排序了
        for (int i = 0; i < k; i++) {
            result.add(nums[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {7, 8, 9, 5, 3, 4};
        Stack03 stack03 = new Stack03();
        ArrayList<Integer> integers = stack03.get(arr, 4);
        for (Integer pre : integers) {
            System.out.print(pre+"");
        }
        System.out.println("");
        ArrayList<Integer> byFast = stack03.getByFast(arr, 4);
        for (Integer pre : byFast) {
            System.out.print(pre);
        }
    }
}

/**
 * 快速排序
 */
class FastOrder {
    public void asc(int[] arr) {
        int min;//最小索引
        int temp;//中间介质
        for (int i = 0; i < arr.length - 1; i++) {//控制循环次数
            min = i;
            for (int j = i + 1; j < arr.length; j++) {//从无序区选取最小的记录
                if (arr[min] > arr[j]) {//如果最小数索引的数比后面的数大就和该数交换索引
                    min = j;//交换索引，循环重复后得出最小的数的索引
                }
            }
            if (min != i) {//如果最小数的索引和一开始引用的数的索引不想等，那么就做一个替换。
                temp = arr[i];//把一开始引用的数传给中间介质，也就是较大值
                arr[i] = arr[min];//把最小数传到一开始定位的位置
                arr[min] = temp;//把中间介质传给最小数，把大值赋值给min位置
            }
        }
//        for (int i = 0; i < arr.length; i++) {//再次遍历数组输出数据
//            System.out.print(arr[i] + " ");
//        }
    }

    public void des(int[] arr) {
        int max;//最大值索引
        int temp;//中间介质
        for (int i = 0; i < arr.length - 1; i++) {//控制循环次数
            max = i;
            for (int j = i + 1; j < arr.length; j++) {//从无序区选取最小的记录
                if (arr[max] < arr[j]) {
                    max = j;
                }
            }
            if (max != i) {
                temp = arr[i];
                arr[i] = arr[max];
                arr[max] = temp;
            }
        }
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
    }

    public static void main(String[] args) {
        FastOrder fastOrder = new FastOrder();
        int[] arr = {3, 4, 1, 8, 9, 0, 3};
        fastOrder.asc(arr);
        for (int pre : arr) {
            System.out.println(pre);
        }
    }
}
